import random
from typing import List


class Solution(object):
    """
    方法：堆排序
    使用最大堆进行排序，首先构建最大堆，然后不断将堆顶元素（最大值）与末尾元素交换，并调整堆结构

    Args:
        nums: List[int], 待排序的数组

    Returns:
        List[int]: 排序后的数组

    Time: O(nlogn), 建堆O(n)，每次调整堆O(logn)，共调整n次
    Space: O(1), 原地排序，不需要额外空间
    """
    def sortArray(self, nums):
        def heapify(n, i):
            largest = i
            left = i * 2 + 1
            right = i * 2 + 2
            if left < n and nums[left] > nums[largest]:
                largest = left
            if right < n and nums[right] > nums[largest]:
                largest = right
            if largest != i:
                nums[i], nums[largest] = nums[largest], nums[i]
                heapify(n, largest)

        n = len(nums)
        # build heap
        for i in range(n // 2 - 1, -1, -1):
            heapify(n, i)
        # Extract the maximum value one by one
        for i in range(n-1, 0, -1):
            nums[0], nums[i] = nums[i], nums[0]
            heapify(i, 0)
        return nums

    """
    方法：快速排序
    使用分治法，通过选取基准值将数组分为两部分，分别对左右部分递归排序

    Args:
        nums: List[int], 待排序的数组

    Returns:
        List[int]: 排序后的数组

    Time: O(nlogn), 平均情况下每次划分将问题规模减半
    Space: O(logn), 递归调用栈的深度
    """
    def sortArray1(self, nums: List[int]) -> List[int]:
        def quick_sort(left, right):
            if left >= right:
                return
            
            # 分区操作
            pivot = partition(left, right)
            # 递归排序左子数组
            quick_sort(left, pivot - 1)
            # 递归排序右子数组
            quick_sort(pivot + 1, right)

        def partition(left, right):
            # 随机选择pivot
            pivot_idx = random.randint(left, right)
            pivot = nums[pivot_idx]
            nums[left], nums[pivot_idx] = nums[pivot_idx], nums[left]
            j = left + 1
            k = right
            while j <= k:
                while j <= k and nums[j] < pivot:
                    j += 1
                while j <= k and nums[k] > pivot:
                    k -= 1
                if j <= k:
                    nums[j], nums[k] = nums[k], nums[j]
                    j += 1
                    k -= 1
            # 将pivot元素放到最终正确位置（j-1处）
            nums[left], nums[j-1] = nums[j-1], nums[left]
            return j - 1

        quick_sort(0, len(nums) - 1)
        return nums
        

    def sortArray2(self, nums: List[int]) -> List[int]:
        def quick_sort(left, right):
            if left >= right:
                return
            
            # 分区操作
            pivot = partition(left, right)
            # 递归排序左子数组
            quick_sort(left, pivot - 1)
            # 递归排序右子数组
            quick_sort(pivot + 1, right)

        def partition(l, r):
            # 随机选择pivot
            pivot_idx = random.randint(l, r)
            pivot = nums[pivot_idx]
            nums[l], nums[pivot_idx] = nums[pivot_idx], nums[l]
            i = l + 1
            j = r
            while True:
                while i <= r and nums[i] < pivot:
                    i += 1
                while j >= l + 1 and nums[j] > pivot:
                    j -= 1
                if i > j:
                    break

                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
            nums[l], nums[j] = nums[j], nums[l]
            return j

        quick_sort(0, len(nums) - 1)
        return nums